It is well known in the art to store data on magnetic or optical disk drives. Generally, data is stored on a disk drive on one or more tracks of predetermined format disposed on a disk-shaped recording media. The data is written to and read from the tracks in response to a read/write command issued by a host computer.
When a hard disk drive has more than one command to execute, the commands are placed in a queue from which the next command is chosen. A Rotational Position Optimization (RPO) algorithm is used to reorder the commands for execution.
Presently, many hard disk drives use a Shortest Access Time First (SATF) RPO algorithm to determine which command to select. This algorithm works as follows: given a set of commands in a queue, choose the command that can be started (accessed) first. This calculation has two parts, the time to perform the seek and settle operation from the current cylinder to the target cylinder, and the latency between this point and the starting sector for the command. Together, these two parts make up the expected access time (EAT) for each queued command. Stated differently, EAT is the time required from the completion of one command to the start of the next, plus one revolution multiplied by the probability of a seek, read, or write error.
The SATF RPO algorithm depends on accurate estimates of the expected access time. If the estimate is too low, the actuator may settle on track after the desired sector has passed rotationally, resulting in a “miss” which adds one full revolution to the access time, thus degrading performance. If the estimate is too high, the optimal command candidate is not chosen for execution.
One key problem with a typical SATF RPO algorithm is that commands may remain in the queue unselected for an indeterminate amount of time. The “maximum service time” metric, provided by common benchmarking programs such as Intel's IOMETER, gives an indication of how long commands can remain unselected for a given workload. Although RPO algorithms attempt to maximize overall throughput, this comes at the expense of responsiveness and an increase in maximum service time.
While RPO attempts to maximize overall throughput, a FIFO (First-in-First-out) style command selection process minimizes the maximum command service time over a period of testing. In a FIFO queue, the oldest command in the queue is always selected for execution. This type of selection process insures that all commands have equivalent service times, and this service time is proportional to the depth of the command queue. The average service time for a FIFO queue might be longer than for a reordered queue since the command have higher latency, but the maximum service time over a testing period using the FIFO queue will be the lowest achievable value.
Several other simple techniques have been employed in order to prevent system-level command timeouts and control maximum service time. The most common solution is to force selection of a command if it has been unselected for a predetermined amount of time. This amount of time is typically specified by a customer via a vendor unique mode page byte. This method of command aging is often referred to as a queue timer scheme.
A significant problem with the queue timer scheme is that for certain workloads and queue timer settings, commands may be forced for selection one after another. This occurs because when one or more commands meet the queue timer criteria, a suboptimal command is executed. This command has a longer than average command time, which often causes other commands in the queue to be forced for selection on the next sort. Eventually, all commands in the queue are executed in the order they are received, and reordering does not resume until the queue is completely emptied.
Another approach to make RPO more “age aware” is described in co-pending application, Ser. No. 09/995,368, entitled “Command Aging Method for Data Storage Devices”, filed Nov. 27, 2001, hereby incorporated by reference. In this approach, older commands are gradually biased for selection before they would be normally selected. This bias can be added to the RPO score, favoring it for selection during a command sort. While this approach effectively prevents the problems caused by the queue timer approach, the performance penalty can still be unpredictable.
There is a need for a system and method to reduce maximum service times under random queued workloads. This system and method should execute the oldest command in the queue at a constant and predetermined rate, in order to yield a minimal, yet predictable performance penalty, while reducing maximum service time dramatically.
The details of the present invention, both as to its structure and operation, can best be understood in reference to the accompanying drawings, in which like reference numerals refer to like parts.